The present invention is in the area of hardware and software for data packet routers, and pertains more particularly to methods for ensuring common physical routing for, in particular, IP packets, and for load balancing in packet routing among physical interfaces.
The growth and development of the public network known as the Internet is a very well-known phenomenon. The Internet has grown very rapidly both in terms of end users and content providers. This phenomenal growth has generated a great need for improved hardware and software for handling the greatly increased data traffic.
Hardware-software systems known as routers are the workhorses of the Internet. In current art most routers are capable of handling traffic at rates in the gigabit per second range. The present inventors are engaged in developing Terrabit routers, and in proposing and developing solutions for problems inherent in current art routing systems.
As is well-known in the art, there are several different kinds of packets to be routed in Internet traffic. One type of packet is termed in the art an IP packet. IP packets can be used for all-types of data; including Internet telephony and Internet video streaming. IP packets have header fields defining such as the source and destination for each packet.
In the art of packet routing it is well-known that it is desirable for packets to arrive at a destination in the same order that they were generated at a source. For one reason, out-of-order packets may well cause dropouts in applications such as voice and video communication and the like. Provision may well be made at a destination to re-order packets, but such re-ordering is expensive in processor resources. Such provision is commonly not made, and packets may be lost or discarded in any case.
If there were to be only one hop from a source to a destination, this would not be problem. Since there are invariably several machines through which packets must pass and be processed, and because newer and better routers may employ processing parallelism, attention must be paid to the order of packets.
The packets handled by a router can be logically divided into flows, where each flow is the set of all packets which are being sent from the same origin to the same destination. A group of such flows can be treated as a single flow. Generally speaking, if packets in the same flow are always sent from every system in the order that they were received, the original ordering will be honored. This is therefore an object of the present invention.
Another problem related to the problem of IP packets is a problem of load balancing among multiple physical interfaces. As the number of physical interfaces associated with a router as opposed to the number of virtual, or defined interfaces becomes ever larger the problem of mapping, and IP packets by common routes becomes more difficult, and the problem of efficiently using the capacity of all the physical interfaces grows as well.
In current art when a packet is received at a router the packets headers are read and typically a forwarding table is consulted to determine the next hop for the packet. This next hop table contains, among other things, the identity of the egress interface to be used and how to send the packet internally to that location. A problem in current art is that the egress interface may well be a defined interface comprising several actual physical egress ports. The problem then is one of determining which of the actual physical egress ports to use. One solution is to simply do another software table lookup. This is not difficult for software based routing elements, but is less than ideal for a high-speed hardware based solution where memory space and ASIC pins may well be limited.
What is clearly needed for the new generation of very high-speed and more sophisticated routers is a method and system for mapping IP packets that have common source and destination by strict physical paths, while at the same time accomplishing efficient load balancing along the same physical paths.
In a preferred embodiment of the invention a method for routing packets in a router to egress ports is provided, the method comprising the steps of (a) using a common characteristic of each packet, choosing a set of egress ports from a table of sets of ports associated with said characteristic; (b) processing any one or more addresses or labels of each packet using a common function, producing thereby a numerical processing result for each packet processed; and (c) using all or a portion of the numerical processing result to select a single egress port for each packet from among the egress ports of the set chosen in step (a).
In some preferred embodiments, in step (a), the common characteristic used for a packet to select a set of egress ports is a destination address for the packet, and in some embodiments the result of step (a) is a pointer to a first address of a sequence of addresses in a stored table wherein the set of egress ports is listed. Also in some embodiments the result of step (b) is an offset, which is added, in step (c), to the address of the pointer to select a single egress port. In some preferred embodiments the addresses or labels processed in step (b) are a source/destination address pair, ensuring thereby that packets of common flow egress by a common egress port.
In some embodiments the common function by which addresses or labels of packets are processed is a hashing function, and some of these embodiments the hashing function result is a binary string, and a default subset of the binary string is used to select an egress port in step (c).
Also in some embodiments, in step (c), weighting is applied to egress ports based on different transmission capacities of the ports, such that packets having different processing results in step (b) may none-the-less be routed to a single, higher-capacity port, providing thereby load-balancing between egress ports. In some other embodiments the data packets are MPLS packets, and in step (b), the processing is accomplished on one or more labels in the label stack of individual ones of the MPLS packets. In some cases individual ones of the egress ports have different transmission capacity, and the transmission capacity of a port having the lowest transmission capacity is considered a least denominator, then ports having higher transmission capacity than the least denominator are assigned a whole number multiplier according to a capacity ratio, and the multipliers are used in the routing to ensure that ports having higher capacity are fully utilized.
In another aspect of the invention a packet router is provided, comprising ingress and egress ports; and control circuitry for processing and routing packets. The router is characterized in that the control circuitry uses a common characteristic of each packet to choose a set of egress ports from a table of sets of ports associated with said characteristic, processes one or more addresses or labels of each packet using a common function, producing thereby a numerical processing result for each packet processed, and uses all or a portion of the numerical processing result to select a single egress port for each packet from among the egress ports of the set chosen.
In some preferred router embodiments the common characteristic used for a packet to select a set of egress ports is a destination address for the packet, and in some of these embodiments the result of table lookup is a pointer to a first address of a sequence of addresses in a stored table wherein the set of egress ports is listed. In these cases the processing by a common function produces an offset, which is added to the first address to select a single egress port.
In some embodiments the addresses or labels processed are a source/destination address pair, ensuring thereby that packets of common flow egress by a common egress port. In some of these embodiments the common function by which addresses or labels of packets are processed is a hashing function. The hashing function result may be a binary string, and a default subset of the binary string is used to select an egress port.
In some embodiments weighting is applied to egress ports based on different transmission capacities of the ports, such that packets having different processing results may none-the-less be routed to a single, higher-capacity port, providing thereby load-balancing between egress ports. In some other embodiments the data packets are MPLS packets, and the processing is accomplished on one or more labels in the label stack of individual ones of the MPLS packets. In some cases individual ones of the egress ports may have different transmission capacity, so the transmission capacity of a port having the lowest transmission capacity is considered a least denominator, ports having higher transmission capacity than the least denominator are assigned a whole number multiplier according to a capacity ratio, and the multipliers are used in the routing to ensure that ports having higher capacity are fully utilized.
In yet another aspect of the invention a method for routing packets in a packet router having a plurality of candidate egress ports for individual ones of the packets is provided, comprising steps of (a) mapping sets of candidate egress ports to a common characteristic of individual packets; (b) mapping individual ports in each set to a result of processing one or more addresses or labels of individual ones of packets to be routed by a common function; (c) selecting a set of candidate ports for each packet to be routed by consulting the common characteristic; and (d) selecting a single egress port from the selected set by the result of the processing by a common function the one or more addresses or labels of each packet.
In embodiments of the invention described in enabling detail below as examples, for the first time a system for routing packets among individual ones of sets of egress ports is provided, assuring that packet flows follow common paths and loads are balanced among the ports.